金字塔光流算法在DSP上的实现与优化.doc

金字塔光流算法在DSP上的实现与优化 金字塔光流算法在 DSP 上的实现与优化向奎，张洪刚，付禹铭*（北京邮电大学模式识别实验室，北京 100876）510152025303540摘要：利用嵌入式监控系统完成车辆跟踪时，由于高清图像像素点太多，导致计算量增大，而硬件运算速度又有限制，因而实现实时高清车辆跟踪具有较大困难。文中通过分析金字塔光流算法的运算量分布情况，结合 TMS320DM648 的结构特点，可以综合使用程序结构化、应用层次化的代码优化方法，把开源的金字塔光流算法 C 代码移植到 TMS320DM648 的过程中，实现程序整体优化和分块优化的结合。优化后的跟踪算法能进一步提高程序的并行性和存储器的访问效率，从而在基于 DSP digital signal processor 的嵌入式平台上实现实时高清车辆监控。关键词：金字塔光流算法；车牌跟踪；移植；优化中图分类号：TN919Creation and Optimization of Pyramid Optical FlowAlgorithm by Digital Signal ProcessorXIANG Kui, ZHANG Honggang, FU Yuming Beijing University of Posts and Telecommunications, Pattern Recognition and Intelligent SystemLaboratory, Beijing 100876 Abstract: When using embedded monitoring systems complete vehicle tracking, due to highdefinition image pixels too much, lead to increase amount of calculation, and hardware operationspeed limited, thus realize real-time high definition vehicle tracking has great difficulties. Throughthe analysis of pyramid optical flow computation algorithm of distribution, combined with thestructure of the TMS320DM648 characteristics can be comprehensive use program structured,application hierarchical code optimization method, the open source pyramid optical flowalgorithm C code transplanted into TMS320DM648 platform, which realize the program wholeoptimization and block optimization. The optimized algorithm can further improve the program ofparallelism and memory access efficiency, thus based on DSP digital signal processor embeddedsystem realizes the real-time high definition vehicle monitoring.Keywords: Pyramid Optical Flow Algorithm; License Plate Tracking; Transplants; Optimization0 引言随着人工智能技术的快速发展，各种先进的跟踪技术开始应用到车辆监控领域。然而车辆跟踪技术是车辆监控的一个重点，迄今，不懈的研究工作对车辆跟踪这一课题做出了诸多的解决方案，其中最为经典的跟踪算法是基于背景差、帧间差、光流和模板匹配实现的。但车辆跟踪的实时性对核心算法的复杂度和运算速度做出了限制，跟踪功能的实现应快速、高效。背景差跟踪算法对光照变化和阴影干扰十分敏感，这决定了该方法进行跟踪具有很高的复杂度。帧间差跟踪算法的高效性和对光照变化的鲁棒性适合简单场景下的实时跟踪，但其对运动目标速度和摄像机采图频率的协调性要求较高。模板匹配跟踪算法的实现需要对全图进行搜索寻找最优匹配区域，这也导致该算法计算量大、运算慢，不适合实时应用。光流法是通过检测图像像素点的强度随时间的变化进而推断出物体移动速度及方向的方法，其实现较为容易，而且运算量较小，有利于实现实时跟踪。目前的车辆跟踪算法大多数都是对整个车进行跟踪，需要对很大的图像区域进行处理，很难实现车辆的实时跟踪1 。作者简介：向奎，（1986-），男，硕士，主要研究方向：智能视频分析。通信联系人：张洪刚，（1974-），男，副教授，主要研究方向：网络图像、视频检索及过滤、机器视觉。E-mail: zhhg-1-本文提出了金字塔光流算法在 DSP 处理器上进行车牌实时跟踪的方案，文中先利用检45测算法获取车牌目标，然后利用金字塔光流算法进行实时跟踪。但把金字塔光流算法应用到嵌入式系统时，由于硬件资源的限制，需要进行各种优化才能够满足实时性的要求。文章结构安排如下：第一部分是背景介绍，第二部分是跟踪算法实现，第三部分是跟踪算法优化，第四部分是实验结果，最后是总结。1 金字塔光流跟踪算法实现501.1金字塔光流算法实现光流是一种简单实用的图像运动的表达方式，通常定义为一个图像序列中的图像亮度模式的表观运动，即空间物体表面上的点的运动速度在视觉传感器的成像平面上的表达。光流法跟踪运动物体的基本原理是：给图像中的每一个像素点赋予一个速度矢量，这就形成了一个图像运动场，在运动的一个特定时刻，图像上的点与三维物体上的点一一对应，5560这种对应关系可由投影关系得到，根据各个像素点的速度矢量特征，可以对图像进行动态分析。如果图像中没有运动物体，则光流矢量在整个图像区域是连续变化的。当图像中有运动物体时，目标和图像背景存在相对运动，运动物体所形成的速度矢量必然和邻域背景速度矢量不同，从而检测出运动物体及位置。采用光流法进行运动物体检测的问题主要在于大多数光流法计算耗时，实时性和实用性都较差。但是光流法的优点在于光流不仅携带了运动物体的运动信息，而且还携带了有关景物三维结构的丰富信息，它能够在不知道场景的任何信息的情况下，检测出运动对象。综上所述，光流算法的实质就是求解公式 1 所示的光流方程。?I?x?IIV 1 上述光流法跟踪基本原理其核心是求解光流方程，虽然上述光流法能够进行物体跟踪，但无法对移动距离较大的目标实现跟踪，因而需要使用金字塔方法缩放图像，来满足光流法65的约束条件，实现模型如图 1 所示。金字塔每增加一层图像缩小 1/4,像素点之间的距离减少1/2，一般 5 层金字塔即可满足光流约束条件。图 1金字塔光流法模型70跟踪系统仅使用一次金字塔算法其跟踪效果不佳，为了提升跟踪算法的准确性，文中选择车牌作为跟踪目标，同时两次运用金字塔光流法来实现高效的跟踪，具体实现过程如下：1） 利用定位算法定位车牌区域，均匀提取车牌区域中的一些像素点；-2-2） 把第一步提取的像素点放入光流算法中，进行第一次光流预测；3） 把第二步预测准确的像素点放入光流算法中，反向进行光流预测；754） 求取原始像素点和反向预测像素点的相似度，修正车牌位置。由于车牌定位技术已经非常成熟，文中直接使用投影卷积算法定位出车牌目标，其具体实现方法文中不做分析，第四步中像素点之间的相似度文中选择欧氏距离进行判断。通过以上四个步骤即可实现金字塔光流跟踪2。801.2金字塔光流算法移植算法移植就是将在 PC 机上的程序移植到 DSP 平台上，并针对 DSP 特点及具体应用进行改写，以使其能够达到实时要求。常见的移植主要是完成两个任务。第一，消减冗余。开源的金字塔光流算法不仅留有许多接口，而且还包含了冗余代码，如大量 trace 信息、assert 信息、printf 函数和 SSE 优化，这些信息在 DSP芯片上对金字塔跟踪算法没有任何必要。85第二，重新编写原程序的头文件。由于 DM648 DSP 的 CCS 代码开发环境具有比 VC 更为严格的编译环境，因此，如果将 PC 版的程序简单照搬到 DSP 上是无法编译的，如在 VC 下的 int64 在 DSP 中应使用 long 代替，并且 CCS 所需要的头文件不需要手动添加，系统会自动进行扫描3。2 金字塔光流跟踪优化902.1浮点转定点优化文中选择的 DSP 处理器是一款定点 DSP 芯片，它在进行浮点运算时，会先把浮点数转换成定点数，然后再进行运算，这样增加了许多计算量，影响了算法的实时性。为了提升浮点数的运算效率，文中利用 Q 格式对浮点数进行定点化。当假定小数点位于第 0 位的右侧时，为 Q0；当把小数点定位于第 15 位的右侧时，为 Q15 ，95例如：16 进制数 2000h 8192，用 Q0 表示；16 进制数 2000h 0.25，用 Q15 表示。浮点数和定点数之间的转换公式如下:Q100定点数 xq 转换为浮点数 x f 时, x f float xq 2? Q 。经过浮点转定点优化之后，再进行相应的运算，可以提升金字塔光流跟踪算法的整体性能，对在 DSP 平台上实现实时车辆跟踪提供了很大帮助。2.2微分优化金字塔光流跟踪算法的核心是求解光流约束方程，但求解方程的过程就会涉及到图像的105110微分，如何实现高效的微分也就成了一个热点。特别是在对高清图像进行处理时，对全图进行微分运算会严重影响算法的实时性能。文中所利用的微分优化方法主要减少存储器访问次数。如图 2 所示，图像中的每一个像素点都需要跟后面这个模版进行运算，图中 7 个像素点都进行微分需要 21 次读取存储器，并且会进行 21 次乘法运算，而如果同时读取这 7 个像素点信息并并行计算它们的微分，仅需要 7 次读取存储器，同时会减少 5 次乘法运算。类似如-3-果把此方法应用到全图，可以大量减少计算量和读取存储器次数，大幅度提升金字塔光流算法的实时性45。115图 2微分示意图2.3图像大小优化文中所设计的跟踪算法的目标是车牌，而车牌仅占图像中的很小一部分，如果对全图进行金字塔光流跟踪，必然会对很多无效的像素点进行运算，因此，金字塔光流算法跟踪图像的大小也是系统优化的一个重点。为了尽可能的剔除掉无用的像素点，文中对相邻两帧图像120中车辆移动的最大距离进行了大量统计。经过统计发现，相邻两帧图像中的车辆最大移动距离小于 360 个像素点，这就表明金字塔光流算法只需要对这 360 360 大小的图像进行跟踪，就可以实现对全图跟踪的效果，图 3 中红色线条距离就是车牌的移动距离。图 3 连续两帧车牌移动距离1253 实验结果通过以上的研究即可在 DSP 上实现车牌跟踪，为了验证文中所设计跟踪算法的实时性和高准确度，分别对白天和夜晚时间段进行了测试，并且文对大量的车辆进行了跟踪，选取跟踪数据的平均值作为评价跟踪算法的依据。1303.1金字塔光流法跟踪效果分析金字塔光流算法在 DSP 上实现跟踪效果如图 4 所示，从图中可以看出，文中所实现的跟踪算法能够很好的实现车牌跟踪，并且跟踪过程中不会存在漂移现象。文中分别对白天和夜晚时间段就行了跟踪测试，跟踪准确率都能够达到 96%以上，超过当前交通监控部门所要求的车辆监控标准。135-4-图 4金字塔跟踪算法跟踪效果图1403.2金字塔跟踪算法优化前后实时性分析测试金字塔光流算法在 DSP 上的每一次跟踪时间来衡量该算法是否具有实时跟踪能力，文中分别对优化前和优化后的跟踪算法进行了实验，获得的时间数据如表 1 所示，从表1 中可以发现，经过文中所讨论的这三种优化方法之后，在 DSP 上的金字塔跟踪算法其效率提升了 76.9%，可以充分实现车辆的实时跟踪。145表 1优化前后金字塔跟踪算法耗时评价标准一次跟踪算法时间（ms）优化前26优化后6注：文中跟踪算法针对同样环境进行跟踪。3.3DSP 和 PC 平台上金字塔光流跟踪算法对比分析由于文中把金字塔光流跟踪算法从 PC 平台移植到 DSP 平台，因而也需要对比分析这两150种平台上金字塔跟踪算法的实时性和鲁棒性，具体对比结果见表 2，从表 2 中可以看出，两种平台实现的跟踪效果没有多大差异，它们都能够实现高精度的车辆跟踪，但运算效率上DSP 平台略低于 PC 平台，产生运算效率差异的主要原因在于 PC 平台的金字塔光流跟踪算法使用 SSE Streaming SIMD Extensions 指令集对算法进行了优化，而文中移植到 DSP平台的金字塔光流算法没有进行类似的优化。155表 2DSP 和 PC 平台跟踪对比分析平台DSPPC跟踪准确度97.5%97.9%跟踪时间 ms 75注：文中跟踪算法对 500 辆车进行了跟踪准确统计4 总结160165本文给出了基于 DSP 的车牌跟踪算法，分析实验数据可以得出，文中使用两次光流算法进行车牌跟踪的准确度非常高，几乎不存在跟丢车牌的情况，同时文中所使用的三种优化方法减少了访问存储器的次数，提升了金字塔跟踪算法在 DSP 上的实时性。文中所使用的算法也有少许车牌跟丢现象，出现这种情况的主要在于光照太强或车牌太脏使得文中选取的特征点信息丢失严重，金字塔光流算法无法预测它们的运动趋势。针对 TM320DM648 的嵌入式图像处理系统，充分利用 DSP 适用于快速实现数字信号处理算法的结构优点，综合运用程序结构化、算法简单化的优化方法，克服了高清图像像素