基于非递归迭代投影的实时深空目标检测算法

吴京辉，唐林波，赵保军，邓宸伟，蔡晓芳

(北京理工大学 信息与电子学院，北京 100081)



基于非递归迭代投影的实时深空目标检测算法

吴京辉，唐林波，赵保军，邓宸伟，蔡晓芳

(北京理工大学 信息与电子学院，北京 100081)

针对深空目标信噪比低、干扰多、传统方法无法检测准确性低的问题，提出一种基于非递归迭代投影的快速实时深空目标检测算法.该算法采用由粗到细的检测流程，首先根据图像特征自适应确定迭代投影次数提取所有疑似目标，然后通过邻域判决对目标进行轨迹关联剔除虚假目标，从而实现目标的准确检测.此外，为了提高算法的实时性，针对FPGA并行流水的特点，利用非递归编程架构对算法进行优化，提高了算法的并行度和运行效率.在SOPC硬件平台上的实验表明，该算法能够准确实时检测深空目标，对悬浮实验的圆满成功起到了决定的作用.

深空目标；目标检测；迭代投影；轨迹关联

随着航天技术的发展，深空目标的检测成为近年来图像处理领域的研究热点，对军事和民用具有重要意义[1-3].深空目标在图像上表现为点目标，几乎没有可用的纹理信息和形状特征，因此需要利用目标的连续运动信息来检测.常用的运动目标检测方法包括帧差法[4]、投影法[5]、光流法[6]和基于小波的检测方法[7-8]等.帧差法结构简单，但对序列图像目标运动速度较快、背景变化较大的情况，将无法得到较好的检测效果.投影法计算简单且易于实现，但是多个目标出现遮挡时容易造成漏检.光流法利用运动目标的光流特性进行检测，对噪声敏感且运算复杂.利用小波多分辨率分析能够检测出局部阶跃点，从而有效检测出潜在目标；但是运算复杂，没有特定的硬件支持一般很难满足实时处理的要求.

本文提出了一种基于非递归迭代投影的实时深空目标检测算法.该算法首先用自适应阈值分割对图像进行二值化处理；然后根据图像特征分别在目标区域的水平和垂直方向反复进行迭代投影，直到得到所有目标的位置，为了便于硬件实现，迭代过程采用了非递归的编程思想；最后根据目标运动的连续性利用邻域判决去除图像虚假目标.对大量实际图像的检测和跟踪实验证明本文提出的快速算法很好地解决了检测效果和实时性之间的矛盾.

1 迭代投影深空目标检测

传统交叉投影算法[4]只进行垂直和水平二次投影，实现简单，节约计算量和存储量，然而，当垂直或者水平方向出现目标遮挡时，只进行二次投影得到的区域中会存在多个干扰目标.因此，进行一次交叉投影不能分离所有的目标.本文对交叉投影算法进行改进，在水平和垂直方向采用迭代投影的方法，最终能够检测出所有目标的准确位置.

1.1 自适应阈值分割

由于深空图像背景灰度变化缓慢，因此可以对原始图像进行预处理滤除背景和一部分噪声，并将其转化为二值图像，从而减少迭代投影的计算量.本文采用自适应阈值法把目标和背景进行二值分割，此算法可以适应于不同的背景图像.阈值门限按下式设置：

(1)

式中：T为阈值门限；m为图像灰度均值；σ为图像灰度均方差；k根据图像的信噪比决定，k=Ck×RSN.其中Ck为调节因子，经验值为Ck∈(0.25，0.85)，RSN为图像幅值信噪比，其定义为

(2)

式中f(x，y)为图像的灰度最大值.

1.2 迭代投影算法1.2.1 传统的交叉投影算法

传统交叉投影算法提取目标的过程如图1所示.首先对二值图像进行竖直投影运算，并检测投影灰度值大于0的坐标区间，则得到相应目标的横坐标区间.在每个区间范围内，对图像进行水平投影检测，进而确定该坐标区间内相应目标的纵坐标范围.这样，经过一次竖直和水平的交叉投影，便可以检测得到相应目标外接4边形的4个顶点坐标.该迭代过程的公式如下：

(3)

(4)

其中:H和W分别为图像的高度和宽度；P(x)和P(y)分别为图像在垂直和水平方向灰度值总和.如果P(x)>0或P(y)>0，则其对应的坐标区域为目标区域.

对于干扰目标比较少的图像经过一次交叉投影就可以检测到各个目标的位置.但是对于比较复杂的图像，会出现多个目标遮挡的情况，如图2所示，只经过一次交叉迭代无法检测出多个目标.

1.2.2 改进的迭代投影算法

针对有目标遮挡的情况，对交叉投影算法进行改进.

投影公式记为

(5)

(6)

式中:下标S表示投影区域;S(y)是投影区域内所有纵坐标的集合；S(x)为投影区域内所有横坐标的集合；PS(x)和PS(y)分别为投影区域内垂直和水平方向灰度值总和.改进的迭代投影算法是根据图像内容，利用投影方程式(5)(6)通过迭代的方式不断寻找所有包含目标的投影区域，直到找到所有目标，迭代终止.

改进迭代投影的具体实现步骤如下：

① 首先对整幅图像进行垂直投影，记录得到的垂直方向上的目标区域Si，记为1级目标区域；

② 在Si区域中再进行水平投影，得到目标区域Sij，记为2级目标区域.

③ 判断每个1级目标区域Si中2级目标区域的个数Sij：若为1，则投影结束；若不是，则在2级目标区域Sij内继续进行垂直投影和水平投影，重复前面的操作，如此迭代直到投影结束.

④ 根据迭代投影得到的外接4边形的坐标就能确定相应目标的位置信息，从而实现了所有目标的检测.

可以看出，以上投影过程不必为所有水平或垂直方向上的像素都进行求和运算，只需对指定区域内像素求和.这种处理方法可以大大节省求和运算时间，提高了系统的工作效率.

步骤③的循环有递归和非递归两种实现方式.递归方法就是将一次垂直投影和一次水平投影作为函数体循环调用，递归终止条件为垂直投影和水平投影的目标区域数均为1.流程图如图3所示.

递归实现具有结构清晰、可读性好、易于理解等优点.然而递归程序较之非递归程序无论是空间需求还是时间需求都更高，另外，有些编译器没有提供递归的机制和手段，如SOPC(system on programmable chip)的Nios Ⅱ硬件加速编译器就不支持递归机制.为了节省存储空间和可以充分利用DSP和FPGA并行流水实现，提高算法的并行度和运行效率，有必要采用非递归方法实现上述迭代投影算法，其流程图如图4所示.

从图4中可以看出，非递归算法实现流程较图3所示的递归算法结构复杂，但是非递归算法不需要存储投影区域，对步骤③的投影过程是流水进行的.因此非递归算法节省了存储空间，提高了投影算法的运行效率.

1.3 轨迹关联

由于深空图像信噪比低且对目标干扰较多，因此单帧的迭代投影目标检测算法无法完全提取出真正的目标，需要利用序列图像目标运动的连续性即多帧轨迹关联进一步剔除噪声提取出真正的目标，本文采用邻域判决的检测算法[9]，基于迭代投影的邻域判决检测算法步骤如下：

① 开始输入连续的N帧图像，初始化计数器为0；② 将第一帧图像作为当前帧，若第一帧为图像序列中的首帧，则对整幅图像进行上述的迭代投影，否则，在以上一次的检测结果为中心的邻域内进行迭代投影，找出二值图像中所有候选目标，记录它们的形心坐标位置；③ 对候选目标，在下一帧图像中以其形心位置为中心对应的邻域内进行迭代投影，观察是否有候选目标点存在：如果有，则记录该帧中可疑目标形心的位置，计数器加1，并将其设为当前位置，重复前面的操作，如果没有，则跳过该帧，转到下帧继续搜索；④ 重复执行步骤③的操作，直到N帧图像全部搜索完毕；⑤ 处理完N帧图像后，判断计数器的输出值：如果计数器值≥i，则判定为真实目标，并标记其位置；否则将其剔除；⑥ 转至下一个候选目标形心位置，对其执行③～⑤各步操作，直到当前帧图像中的所有侯选目标都被处理过一遍；⑦ 更新N帧图像，转至步骤②继续执行判决过程，直至处理完整个图像序列.

关联的帧数N由处理时间和缓存空间共同决定，i=CiN，其中Ci为调节因子，经验值为Ci∈(0.6，0.8)，邻域窗口大小可根据实际情况进行调整，目标运动速度较慢时，可减小窗口的大小，以便节省时间，目标运动速度较快时，要适当扩大窗口的大小，以保证真实的目标点落在邻域范围内.其流程图如图5所示.

2 实验结果与分析

本文用VC++6.0产生模拟的图像序列，序列大小为128×128，目标按照椭圆轨迹运动，并在图像序列中加入干扰和噪声.在所研制的基于SOPC的硬件平台上进行实验验证，结构框图如图6所示.

其中，成像器负责采集和传输数字图像；FPGA对图像进行预处理，对原始图像进行自适应阈值分割； SOPC核Nios Ⅱ CPU完成目标检测，主要完成迭代投影算法和基于邻域判决的轨迹关联算法，并在检测到的目标位置画十字；DPRAM存储中间结果；SRAM缓存图像数据；通信模块负责主控计算机和板卡的通信及控制，通信模块收到主控计算机的数据后，进行命令解析，按照解析后的指令向开关量发送控制信息.同时将目标位置和目标状态参量发送给主控计算机.

实验中N=4，Ci=0.75，则i=3，即只关联了4帧连续图像，邻域窗口选取32×32的窗口.仿真结果如图7所示.

图7(a)是用VC++6.0产生的原始图像，图7(b)是自适应阈值分割的结果；图7(c)和 7(d)分别是用递归和非递归方式得到的目标检测结果，方框点为真实目标，其余点都是干扰；图7(e)～7(h)为从序列图像中随机抽取的部分检测结果.由图7可知，自适应阈值分割处理能滤除大部分噪声，运用递归和非递归方法实现迭代交叉投影检测方法均能准确检测出所有的目标点，运用邻域判决的方法进行4帧轨迹关联最终准确检测出真实的目标.

可以看出，本文的方法在干扰较多的情况下，仍然能够准确检测目标，由于目标较小，因此检测到目标的位置不会出现偏差.为突出本文算法的性能，分别从检测率和虚警率[10]方面与传统投影算法进行比较.实验共产生了500幅含有目标和噪声的图像，对500幅图像进行目标检测，统计检测率和虚警率，结果如表1所示.

表1 检测率和虚警率对比

从表1可以看出，检测率比传统投影算法提高了5.8%，虚警率降低了3.2%.因此改进后的算法的检测性能有明显提高.

为了测试本文算法的优化效果，分别对递归和非递归实现的两段代码进行多次执行，并记录执行时间.实验结果如表2所示.

表2 递归和非递归方法的执行时间

Tab.2 Execution time of recursive and non-recursive approaches

程序执行次数递归方法/ms非递归方法/ms1003116100040678100004109797

从表2可以看出，程序执行100次，非递归方法的执行速度是递归方法的1.9倍；程序执行1 000次，非递归方法的执行速度是递归方法的5.2倍；程序执行10 000次，非递归方法的执行速度是递归方法的5.1倍.实验结果表明，非递归方法比递归方法效率至少提高1.9倍.

算法实时性要求目标检测可以在一帧图像的消隐期完成.通过以上计算时间的分析，可以看出程序执行一次的时间在1 ms以内，满足实时性要求.

3 结 论

提出了一种改进的非递归迭代交叉投影深空目标检测算法，该方法根据深空目标图像的信噪比进行自适应阈值法分割，然后采用结合迭代投影的邻域判决方法进行多帧轨迹关联，可以实现在深空背景下沿特定轨迹运动的目标的准确检测.相对于传统的交叉投影法，迭代投影能够适用于更复杂的图像，适用范围更广.为了满足FPGA并行流水实现的特点，本文在算法的实现上采用了非递归机制进行优化，可以实现硬件加速，提高了算法的执行效率，达到了实时性要求.

VC软件平台仿真结果表明，在深空背景下目标沿椭圆轨迹运动时，该算法取得了较好的检测效果.基于SOPC硬件平台的实验结果表明，该算法具有很强的抗干扰能力，满足图像处理的实时性要求，具有较好的移植性.

[1] Lipton A J，Fujiyoshi H，Patil R S.Moving target classification and tracking from real-time video[C]∥Applications of Computer Vision Proceedings of Fourth IEEE Workshop on.[S.l.]: IEEE，1998:8-14.

[2] 高建伟，李磊，姚睿，等.基于卡尔曼滤波的弱小目标实时检测与跟踪[J].计算机工程，2012，38(2):4-7.

Gao Jianwei，Li Lei，Yao Rui，et al.Real-time detection and tracking for dim-small target based on Kalman filtering[J].Computer Engineering，2012，38(2):4-7.(in Chinese)

[3] 叶有时，唐林波，赵保军.一种基于聚类的深空红外多目标快速检测算法[J].电子与信息学报，2011，33(1):77-84.

Ye Youshi，Tang Linbo，Zhao Baojun.A fast deep-space infrared multi-target detection algorithm based on clustering[J].Journal of Electronics &Information Technology，2011，33(1):77-84.(in Chinese)

[4] 甘明刚，陈杰，刘劲，等.一种基于三帧差分和边缘信息的运动目标检测方法[J].电子与信息学报，2010，32(4):894-897.

Gan Minggang, Chen Jie, Liu Jin, et al.Moving object detection algorithm based on three-frame-differencing and edge information[J].Journal of Electronics &Information Technology，2010，32(4):894-897.(in Chinese)

[5] 王兆魁，张育林.一种CCD星图星点快速定位算法[J].空间科学学报，2006，26(3):209-214.

Wang Zhaokui，Zhang Yulin.Algorithm for CCD star image rapid locating[J].Chinese Journal of Space Science，2006，26(3):209-214.(in Chinese)

[6] 周斌，王军政，沈伟.动态跟踪中背景补偿与目标运动估计[J].北京理工大学学报，2010，30(11):1305-1309.

Zhou Bin，Wang Zhengjun，Shen Wei.Background compensation and motion estimation for dynamic tracking[J].Transactions of Beijing Institute of Technology，2010，30(11):1305-1309.(in Chinese)

[7] 张旭光，韩广良，孙巍，等.复杂背景下运动目标的提取[J].光电工程，2006，33(4)：10-13.

Zhang Xuguang，Han Guangliang，Sun Wei, et al.Extraction of moving objects in clutter background[J].Opto-Electronic Engineering，2006，33(4):10-13.(in Chinese)

[8] 盛文，邓斌，柳健.一种基于多尺度距离像的红外小目标检测方法[J].电子学报，2002，30(1):42-45.

Sheng Wen，Deng Bin，Liu Jian.Multi-resolution distance map based small target infrared image[J].Acta Electronica Sinica，2002，30(1):42-45.(in Chinese)

[9] 王鹏，陈国瑛.可见光图像序列中运动弱小目标检测方法研究[J].现代防御技术，2008，36(1):114-120.

Wang Peng，Chen Guoying.Research of moving weak small target detection method in optical image sequences[J].Modern Defense Technology，2008，36(1):114-120.(in Chinese)

[10] 张弘，赵保军，史彩成.对低信噪比下的红外点目标高检测率的研究[J].系统工程与电子技术，2001，23(3):58-60.

Zhang Hong，Zhao Baojun，Shi Caicheng.The study of high detecting probability of infrared point target under low SNR[J].Systems Engineering and Electronics，2001，23(3):58-60.(in Chinese)

(责任编辑：刘芳)

Deep-Space Object Detection Based on Non-Recursion Iterative Projection

WU Jing-hui，TANG Lin-bo，ZHAO Bao-jun，DENG Chen-wei，CAI Xiao-fang

(School of Information and Electronics，Beijing Institute of Technology，Beijing 100081，China)

Traditional method could not detect all objects, when the deep-space image is low SNR and full of distortion.To tackle this problem, a fast and real-time deep-space object detection approach was proposed, which was based upon modified iterative projection and non-recursion programming method.In this algorithm, a coarse-to-fine detection process was used.Firstly, the number of projection was determined adaptively in accordance with the image unique properties to detect all objects.Then the trajectory matching was undergone by neighborhood decision approach to achieve accurate objects detection.To implement the algorithm in real time, a non-recursion program method was used to optimize the structure of the hardware.So, the proposed algorithm was easy to implement by FPGA.Experimental results on SOPC hardware platforms show that it can perform real-time detection accurately for the deep-space objects, and it plays a decisive role for the success of the experiment on suspension.

deep-space objects;object detection;iterative projection;trajectory matching

2013-11-08

国家“八六三”计划项目

吴京辉(1984—)，男，博士生，E-mail:wjinghui@bit.edu.cn.

TP 391

A

1001-0645(2016)03-0314-06

10.15918/j.tbit1001-0645.2016.03.017