HartSift: 一种基于GPU的高准确性和实时SIFT

尺度不变特征变换 (SIFT) 是最流行和最强大的特征提取算法之一，因为它对尺度、旋转和光照保持不变。它已被广泛应用于视频跟踪、图像拼接、同时定位和映射（SLAM）、运动结构（SFM）等领域。然而，高计算复杂度限制了其在实时系统中的进一步应用。这些系统必须在准确性和性能之间进行权衡以实现实时特征提取。他们采用其他更快但精度较低的算法，如 SURF 和 PCA-SIFT。为了解决这个问题，本文提出了一种使用 CUDA 的 GPU 加速 SIFT，命名为 HartSift，充分利用单机CPU和GPU的计算资源，实现高精度、实时的特征提取。实验表明，在 NIVDIA GTX TITAN Black GPU 上，HartSift 可以根据图像的大小在 3.14-10.57ms (94.61-318.47fps) 内处理图像。此外，HartSift 分别比 OpenCV-SIFT（CPU 版本）和 SiftGPU（GPU 版本）快 59.34-75.96 倍和 4.01-6.49 倍。同时，HartSift 的性能和 CudaSIFT（迄今为止最快的 GPU 版本）的性能几乎相同，而 HartSift 的准确度远高于 CudaSIFT。

SIFT算法可以提取大量显著特征，这些特征在缩放、旋转、光照和3D视点保持不变，还提供了跨越噪声和仿射失真的稳健匹配。但SIFT的高计算复杂度限制了其在大规模数据和实时系统中的进一步应用。而复杂度较低的算法，如SURF、PCA-SIFT的准确性又不太高。因此，在主流计算平台上实现高精度、实时的SIFT是一个重要而有意义的研究课题。

而SIFT算法具有很好的并行性，可以正确移植到GPU上。因此，在配备GPU的异构计算系统上实现高性能的SIFT具有重要的实用价值。

SIFT 算法包含三个阶段，包括高斯差分（DoG）金字塔的构建、精确的关键点定位和 128 维描述符生成。由于每个阶段都有自己的并行特性，因此必须使用不同的并行粒度和优化来实现高性能。尤其是后两个阶段，负载不平衡不利于GPU优化，会导致性能下降。

本文的主要贡献和创新可以概括如下：

有许多工作尝试在GPU上使用SIFT算法。

然而，为了实现高性能，他们省略了 SIFT 算法的一些重要步骤，例如将输入图像加倍、保持尺度变化的连续性和拟合二次函数以定位准确的关键点信息。作者的实验表明，这些遗漏会导致 SIFT 丢失很多关键点和准确性。

Lowe将输入图像尺寸加倍作为高斯金字塔 的最底层，每个尺度 通过高斯卷积产生：

高斯金字塔确定之后，利用相同Octave的层级相减，得到差分金字塔：

其中 ，在本文中， .

检测尺度空间极值

将DoG金字塔每个像素与相邻像素比较，同层8个，上下层9个，若像素是局部最大值或局部最小值，将其视为关键点候选。

去除无效关键点

去除较低对比度和不稳定边缘响应的候选关键点，通过将3D二次函数拟合到附近数据执行子像素插值，以获取精确的位置、比例和主曲率比。

方向分配

将候选关键点周围的梯度累积到36 bins的直方图中，根据每层的尺度计算搜索半径。每个紧邻像素由一个高斯加权窗口加权，梯度方向累计到36 bins的方向直方图中。峰值为主要梯度方向，同时超过峰值80%的局部峰值bin也被视为关键点方向。

对关键点周围像素计算梯度直方图，搜索半径比上一步骤大得多，同样用一个高斯加权函数用于为每个邻居的梯度值分配权重。

根据梯度方向将最终的梯度值累积到一个 360-bin 的圆形方向直方图。最后，直方图将被归一化、平滑并转换为 128D 描述符。

构建金字塔应该保持顺序，以保证尺度空间变化连续性。Acharya和Bjorkman为加快这一过程，牺牲准确性打破构建顺序。考虑到不能使准确性降低，构建顺序在HartSift中保留。

分离卷积核

对于 大小的卷积核处理 大小的图像需要进行 次运算，如果将2D卷积核拆解为两个1D的卷积核，计算量减少至 . 通过使用共享内存和向量化方法，更容易实现合并全局内存访问并减少一维卷积的冗余访问。

Uber 内核

Uber内核将多个不同任务放到一个物理内核中，在一个内核中并行处理任务，而不需要在内核之间切换。差分金字塔第 层由高斯金字塔第 和第 层决定。将高斯差分金字塔和高斯卷积核封装在单个核中，可以充分挖掘并行性。

线程不需要重复读取高斯金字塔第 层的值，这是由于第 层的值计算完后，结果会放在寄存器内而不是全局内存中。借助Uber内核的优势，我们可以节省 的空间和 的内核运行时间

异构并行

HartSift 采用异构并行方法来加速这一阶段。CPU 和 GPU 将并行协作，构建 DoG 金字塔。

由于GPU处理小图像没有优势，作者将 以下的图像放到CPU处理，大图像放到GPU处理。用户也可以自行设置分离点，确保CPU和GPU负载平衡。

存在两个问题：

负载均衡

Warp是GPU最小并行执行单元，即以锁步方式执行的 32 个线程的集合。若负载不均衡，则warp执行时间取决于最后一个线程完成的时间，warp负载不均衡会导致GPU效率降低。

由于候选关键点分布的随机性，几乎所有经线都包含不同数量的空闲线程。如果这些warp继续处理以下部分，就会出现两个级别的负载不平衡.

在去除无效的候选关键点部分时，线程将进行亚像素插值以获得准确的候选关键点信息，从而去除具有低对比度或不稳定边缘响应的关键点候选。换句话说，一些线程会比其他线程更早返回一次。负载不平衡会变得更加严重。

为了突破性能瓶颈，HartSift 引入了重新平衡工作负载和多粒度并行优化。

重新平衡工作负载

当检测到负载不平衡时，HartSift 将通过启动具有适当粒度的新内核并分派每个具有 32 个活动线程的新经线来重新平衡工作负载。

此外，启动三个内核分别处理这三个部分，不仅可以重新平衡工作量，还可以根据不同部分的并行特性提供多粒度的并行。

多粒度并行

重新平衡工作负载优化保证每个内核中的线程和经线被完全加载，多粒度并行优化保证工作负载将平均分配到线程和经线。此外，不同内核的并行粒度取决于工作负载的特性。

HartSift通过将一个线程映射到一个或多个像素，采用与关键点候选检测部分和无效关键点去除部分并行的线程粒度。然而，线程粒度并行会导致方向分配部分的负载不平衡，因为不同关键点的相邻区域半径不同。线程粒度并行会为单个线程分配过多的工作，这在某些情况下限制了硬件资源的利用率。所以在这部分应用混合粒度并行：扭曲粒度构建直方图，线程粒度找出并将主导方向分配给相应的关键点。

基于扭曲的直方图算法

作者针对每个关键点提出了一种基于扭曲粒度和原子 *** 作的高性能直方图算法，以充分利用局部性。

该阶段关键点的邻域半径远大于前一阶段。需要为每个关键点累积数千个邻居到一个 360-bin 直方图。如果采用前一阶段的基于原子扭曲的直方图算法，会对这一阶段的性能产生不同的影响。

HartSift引入了一种atomic-free的直方图算法，进一步提升了这一阶段的性能。

该算法包含三个步骤：

为了消除线程间的负载不平衡，实现全局合并访问，HartSift 使用一个warp 来处理一个keypoint 的所有邻居。当线程计算出它们的方向 bin 时，它们需要根据bin变量的值将梯度值累加到局部直方图。考虑到有如此多的邻居并且一个经线的一些线程可能具有相同的 bin，算法1引入了一种无原子的多键约简方法来累积每个经线的部分和。这种方法可以利用warp级shuffle和vote指令完全消除原子 *** 作和本地同步。它根据bin对经纱的线程进行分组并指定每组具有最低车道的线程作为队长线程。队长线程将保存他们自己的 bin 的部分总和，并将它们并行地累积到驻留在共享内存中的本地直方图，而不会发生 bank 冲突和同步。在遍历所有邻居后，HartSift 将最终的局部直方图复制到驻留在全局内存中的全局直方图。

本文提出了一种GPU上的并行SIFT，命名为Hart-Sift，它可以在单机内同时使用CPU和GPU来实现高精度和实时的特征提取。HartSift根据每个阶段的不同特点，通过适当采用不同的优化策略来提升性能，例如负载均衡、基于warp的直方图算法和不同尺度样本的atomic-free直方图算法等。在NVIDIA GTX TITAN Black GPU上，HartSift可以在3.14 ~ 10.57ms（94.61 ~ 318.47fps）内提取高精度特征，轻松满足高精度和实时性的苛刻要求。另外，与OpenCV-SIFT和SiftGPU相比，HartSift获得了59.34 ~ 75.96倍和4.01 ~ 6.49倍加速分别。同时，HartSift 和 CudaSIFT 的性能几乎相同，但 HartSift 远比 CudaSIFT 准确。

1.GPU：计算机图显核心

1.1 GPU：计算机图形显示核心

GPU基本概念：图形处理器（graphics processing unit，缩写GPU），又称显示核心、视觉处理器、显示芯片，是一种专门在个人电脑、工作站、游戏机和一些移动设备（如平板电脑、智能手机等）上做图像和图形相关运算工作的微处理器。

GPU是显卡的处理器：显卡全称显示适配卡，又称显示适配器，用于协助CPU进行图像处理，作用是将CPU送来的图像信号经过处理再输送到显示器上，由主板连接设备、监视器连接设备、处理器和内存组成，GPU即是显卡处理器。

1.2 GPU擅长大规模并发计算

GPU工作原理：GPU的工作通俗的来说就是完成3D图形的生成，将图形映射到相应的像素点上，对每个像素进行计算确定最终颜色并完成输出，一般分为顶点处理、光栅化计算、纹理贴图、像素处理、输出五个步骤。GPU采用流式并行计算模式，可对每个数据行独立的并行计算。

GPU与CPU区别：CPU基于低延时设计，由运算器（ALU）和控制器（CU），以及若干个寄存器和高速缓冲存储器组成，功能模块较多，擅长逻辑控制，串行运算。GPU基于大吞吐量设计，拥有更多的ALU用于数据处理，适合对密集数据进行并行处理，擅长大规模并发计算，因此GPU也被应用于AI训练等需要大规模并发计算场景。

1.3 GPU可分为独立GPU和集成GPU

独立GPU：独立GPU一般封装在独立的显卡电路板上，使用专用的显示存储器，独立显卡性能由GPU性能与显存带宽共同决定。一般来讲，独立GPU的性能更高，但因此系统功耗、发热量较大。

集成GPU：集成GPU常和CPU共用一个Die，共享系统内存。集成GPU的制作由CPU厂家完成，因此兼容性较强，并且功耗低、发热量小。但如果显卡运行需要占用大量内存，整个系统运行会受限，此外系统内存的频率通常比独立显卡的显存低很多，因此一般集成GPU的性能比独立GPU更低。

1.4 GPU广泛运用在图显和并行计算场景

GPU拥有单一的强大并行计算能力，所以用途往往是需要大规模并行计算的场景。早期GPU多被用于2D和3D图形的计算和处理，因为图形数据的处理往往涉及到大量的大型矩阵运算，计算量大但易于并行化。近年由于大数据、人工智能发展，GPU也常常被用于需要大量重复计算的数据挖掘领域，如机器学习，深度学习等。

GPU使用场景：GPU被广泛地运用于PC、服务器、移动等领域。其中服务器GPU可做专业图形处理、计算加速、深度学习等应用，以独立GPU为主；移动端GPU主要采用集成GPU；PC根据使用用途不同，既可以搭载独立GPU，也可以使用集成GPU。

1.5 全球GPU巨头：NVIDIA、AMD

NVIDIA（英伟达）：创立于1993年，1999年发明了GPU，最初专注PC图形，后来拓展到密集计算领域，Nvidia利用GPU创建了科学计算、人工智能、数据科学、自动驾驶汽车、机器人技术、AR和VR的平台。 Nvidia是目前全球最大的独立GPU供应商，2020年营收166.8亿美元，2021Q2 Nvidia全球独立GPU市场份额达到83%。

AMD（超威半导体）：成立于1969年，目前业内稀缺的可以提供高性能CPU、高性能独立显卡GPU、主板芯片组三大组件的半导体公司。2020年AMD营收97.6亿美元，其中计算和图形（包括CPU、GPU、APU等）业务营收64.3亿美元，2021Q2 AMD全球独立GPU市场份额达到17%。

2.GPU两大应用场景：图显、计算

2.1 2020全球GPU市场规模接近千亿美元

2020年全球GPU市场规模达到999.1亿美元。3D图像显示、人工智能深度学习的需求支撑GPU市场持续增长，根据Verified Market Research数据，2020年全球GPU市场规模达到999.1亿美元，预计2028年达到1581.6亿美元，CAGR为5.9%。

测算2020年中国大陆独立GPU市场规模约235亿美元。中国是全球GPU市场重要组成部分，2020年Nvidia、AMD在中国大陆收入占比分别为23.3%、23.9%，我们假设中国大陆独立GPU市场占全球23.5%，测算2020年中国大陆独立GPU市场规模约为235亿美元。

2.2 PC GPU：2020年全球出货3.94亿片

PC（个人电脑）是GPU重要应用场景，根据Jon Peddie Research（JPR）数据，2020年全球GPU出货3.94亿片，同比增长17.9%。

2.3 PC GPU：Nvidia和AMD占据独立GPU市场

Intel领导集成GPU市场。Intel（英特尔）是全球最大的CPU制造商，2021Q2占据全球77.5%的x86 CPU市场，集成GPU集成在CPU中，Intel凭借CPU市场地位，占据全球PC GPU大部分市场。根据JPR数据，2021Q2 Intel占据全球68.3%的PC GPU市场份额，Nvidia和AMD市场份额分别为15.2%、16.5%。

Nvidia和AMD占据独立GPU市场。在独立GPU领域，Nvidia具备明显的份额领先，2021Q2市占率达到83%。2006年AMD收购ATI，2010年放弃ATI品牌后推出AMD Radeon（镭龙）独立显卡系列，2021Q2 AMD独立PC GPU市场份额17%。

2.4 AI服务器与加速芯片

AI服务器：通常搭载GPU、FPGA、ASIC等加速芯片，利用CPU与加速芯片的组合可以满足高吞吐量互联的需求，为自然语言处理、计算机视觉、机器学习等AI应用场景提供强大的算力支持，支撑AI算法训练和推理过程。

AI加速芯片：由于CPU并不适合大规模并行计算，因此需要加速芯片执行AI算法，目前AI加速芯片主要包括图形处理器（graphics processing unit，GPU）、现场可编程门阵列（field-programmable gate array，FPGA）、专用集成电路（application specific integrated circuits，ASIC）、神经拟态芯片等。

2.5 GPU是AI服务器首选加速方案

服务器是AI核心基础设施。根据IDC数据，2020年中国AI基础设施市场规模为39.3亿美元，同比增长26.8%，并将在2024年达到78.0亿美元，其中2020年服务器市场规模占AI基础设施的87%以上，承担着最为重要的角色。

互联网行业是AI服务器最大采购行业。根据IDC数据，2020年上半年，互联网占整体加速计算服务器市场近60%的份额，同比增持超过100%；政府行业和服务业分别依次位居第二位和第三位。

GPU服务器是AI加速方案首选。IDC预计2021年中国GPU服务器占比91.9%左右的市场份额，是数据中心AI加速方案首选。根据IDC数据，2019年中国GPU服务器市场规模达到20亿美元，预计2024年将达到64亿美元。

2.6 AI服务器通常配置多个GPU芯片

GPU加速服务器能够提供优秀的浮点计算能力，从容应对高实时、高并发的海量计算场景，例如深度学习、科学计算、3D动画渲染、CAE等应用场景。

3.NVIDIA：全球GPU巨头

3.1 全球GPU巨头

Nvidia成立于1993年，1999年上市，市值近10年增长超过83倍，近6年增长超过49倍。截至2021年11月5日，Nvidia总市值7438亿美元，总市值美股排名第七，是目前全球市值最大的半导体公司。（报告来源：未来智库）

3.2 三大因素推动地位提升

技术革新、场景拓展、外延并购，Nvidia引领全球GPU发展。

GPU架构：Nvidia坚持每2-3年推出一代新的GPU架构，持续保持技术领先，新的Ampere已经采用7nm工艺；应用场景：从最初图形处理到通用计算，再到AI深度学习和自动驾驶，Nvidia不断推动GPU应用场景的突破；外延并购：2000-2008年Nvidia密集收购额多家公司，涵盖显卡、图形处理、半导体等多个领域，2020年宣布计划收购ARM。

3.3 近年业绩高速增长

Nvidia产品主要分为两大类：图形处理、计算&网络。下游市场包括游戏、专业可视化、数据中心、汽车四大类。

2020年Nvidia营收166.8亿美元（yoy+52.7%），净利润43.3亿美元（yoy+54.9%），其中图形处理业务营收98.3亿美元，计算&网络业务营收68.4亿美元。除去2019年游戏市场需求波动造成业绩下滑外，Nvidia近5年营收、利润均保持较快增长。

得益于基于Ampere架构新GPU产品带动游戏业务高增，以及数据中心对算力需求旺盛，2021上半年Nvidia营收、净利润快速增长。

3.4 游戏是最大市场，数据中心市场增速较快

Nvidia下游市场分为四类：游戏、专业可视化、数据中心、汽车，各市场重点产品如下：

游戏：GeForce RTX/GTX系列GPU（PCs）、GeForce NOW（云游戏）、SHIELD（游戏主机）；专业可视化：Quadro/RTX GPU（企业工作站）；数据中心：基于GPU的计算平台和系统，包括DGX（AI服务器）、HGX（超算）、EGX（边缘计算）、AGX（自动设备）；汽车：NVIDIA DRIVE计算平台，包括AGX Xavier（SoC芯片）、DRIVE AV（自动驾驶）、DRIVE IX（驾驶舱软件）、Constellation（仿真软件）。

3.5 计算业务驱动高成长

计算业务是Nvidia成长的主要驱动力：数据中心已成规模，智能汽车将进入收获期。

在数据中心市场，Nvidia拥有芯片、硬件、硬件的全栈布局。得益于全球AI应用场景的快速增加，对算力的需求飙升。是Nvidia成长最快的市场，2020年营收达到约66.96亿美元，近4年CAGR达到68.5%，远高于游戏市场的17.6%。2020年Nvidia数据中心市场营收占比已经超过40%，预计未来仍将继续提升。

在智能汽车市场， Nvidia形成了全栈式自动驾驶解决方案。AGX Xavier芯片于2018年开始出货，下一代自动驾驶芯片Orin计划用于2022年量产，算力将达到254TOPS，目前已经获得蔚来、理想、沃尔沃、奔驰等多个整车厂定点项目。我们认为2022年高阶自动驾驶汽车或将集中落地，Nvidia自动驾驶将进入收获期。

3.6 中国大陆收入贡献提升

Nvidia中国大陆收入快速增长。2020年Nvidia来自中国大陆收入38.86亿美元，同比增长42.3%，近4年CAGR达到31.4%，同期Nvidia整体营收CAGR为24.6%。

Nvidia中国大陆收入占比呈上升趋势。2020年Nvidia中国大陆收入占比达到23.3%，相比于2016年的18.9%提升4.4pct，2021上半年Nvidia中国大陆收入占比25.6%，上升趋势明显。

我们预计中国大陆占比仍将提升。图显业务层面，人均收入提升将带动PC需求增加；计算业务层面，目前中国大陆在AI算法、应用层面具有领先优势，自动驾驶场景也将率先得到释放。

4.景嘉微：国产GPU领军

4.1 国内唯一商用GPU公司

景嘉微成立于2006年，公司主营业务分为图形显控、小型专用化雷达、GPU芯片三类。其中图显、雷达产品主要面向军用市场，GPU芯片产品包括JM5400、JM7200，其中JM5400主要应用于公司图显模块中，JM7200成功拓展了民用和信创市场。2021年9月，公司第三代GPU芯片JM9成功流片，目前正在进行性能测试。

4.2 两个系列、三款GPU量产应用

景嘉微已完成两个系列、三款GPU芯片量产应用。第一代GPU产品JM5400于2014年流片成功，主要支撑军用装备，已在国产军用飞机上实现了对ATI M9、M54、M72等芯片的替代；第二代产品JM7200于2018年8月流片成功，性能与 Nvidia的GT640显卡相近。在JM7200基础上，公司又推出

---