数字自动对焦中的搜索算法研究

王剑华，邓华秋，陈参宁

（华南理工大学 物理系，广东广州 510640）

0 引言

伴随IT技术的高速发展，微电子技术、数字图像处理及网络传输技术的发展，各行业对数字视频监控技术的智能需求也不断发展。自动对焦作为视频监控的关键技术之一，已经广泛地应用于一体化视频监控、数码相机、测距等领域中。与测距法和聚焦检测法的传统自动对焦方法相比，基于数字图像处理的自动对焦方法更加灵活方便，有利于设备的集成化、微型化及降低设备的成本。

数字自动对焦中，作为自动控制关键技术的搜索算法，其最终目标是找到对焦评价曲线峰值。对焦搜索过程就是通过比较一系列离散的对焦评价函数值，然后根据分析结果反馈控制对焦镜移动，实质上也是一维极值的最优化问题［1］。

本文通过对典型对焦搜索算法进行研究，改进传统搜索算法，力求设计出优秀的综合对焦搜索算法，目的是为了避免搜索落入对焦曲线局部峰值、提高对焦速度及增强对焦抗干扰性能力。

1 典型的对焦搜索算法

典型的对焦搜索算法有穷举搜索法、爬山搜索法、Fibonacci搜索法和函数逼近法等［2］。

1．1 穷举搜索法

穷举搜索法是最简单与直接的对焦搜索法，示意图如图1所示，搜索区间［a，b］分成若干等间隔的子区间，利用对焦评价函数评价所有区间端点的图像，从得到的所有评价值集合中求出最大值，即是准焦的位置。

穷举搜索法具备的优点是相对简单;步长固定不变，便于计算机自动控制;无穷搜索特点也不受局部峰值的影响。存在的缺点是计算量大，不适用于实时的对焦搜索。

1．2 爬山搜索法

图1 穷举搜索法示意图Fig 1 Schematic diagram of an exhaustive search method

爬山搜索法的前提是对焦评价函数具有单峰性、单调性。作为应用最广泛的一种搜索法，典型示意图如图2所示。首先，对焦镜头向两边方向搜索，评价值增大的方向即为正确的方向，找到镜头搜索方向;其次，对焦镜头越过评价曲线锋值，缩小步进距离，往回搜索并再次越过峰值;最后，缩小步进距离，反复搜索，一直到满足精度要求的峰值即为成像准焦的位置。

图2 爬山搜索法示意图Fig 2 Schematic diagram of climbing search method

爬山搜索法的优点是简单易实现，计算量也易于控制，适合于实时的快速对焦。存在着的缺点是容易陷入到由于噪声等干扰引起的局部峰值附近，导致对焦失败。

Fibonacci搜索法具有存储量少、容易预测不确定区间等优点，但却容易陷入局部峰值，也由于非整步长和对电机的分辨力要求太高而难以实现，只能作为设计搜索算法的参考依据。函数逼近法的最佳用法，是利用峰值左右的几个值，拟合曲线求极值，得到最佳成像位置［3］。

2 基于传统对焦搜索算法的改进

本文是对具有光学变倍的镜头进行自动对焦研究，镜头结构示意图如图3所示。对焦景物从前固定组进入镜头，经变倍镜、光圈、对焦镜及后固定组成像在图像探测器上，变倍镜可以调节所成像的大小，对焦镜能够调节使图像探测器上所成像达到准焦。由镜头设计厂商或者手动测量获得不同物距的成像曲线，即一定物距的景物，对应不同的变倍镜位置都有一个最佳的变焦镜位置使所成像准焦。

穷举搜索法不易受干扰，但却不利于实时性;爬山搜索利于实时要求较高的对焦，但却容易受干扰而陷入局部峰值。对传统搜索法的改进，目的是为了提高对焦收敛速度与增强抗干扰能力。

2．1 改进的穷举搜索法

图3 镜头结构示意图Fig 3 Schematic diagram of the lens’structure

本文把对焦镜可移动范围称为对焦范围。对焦范围过宽会导致:1）对焦收敛速度过慢，例如穷举搜索法;2）对焦镜远离光学对焦范围会使对焦曲线较平坦甚至出现多处局部峰值，搜索算法极有可能会陷入局部峰值误对焦甚至再也无法正常对焦。对焦镜远离光学对焦范围情况下，用爬山搜索等方法无法正常搜索，本文采用改进的穷举搜索法，主要是在对焦范围内设定上下限，并预判定搜索方向，可以避免对焦镜远离光学范围与提高收敛速度。

改进的穷举搜索法如图4所示:1）获取最近（例如:1 m）与最远处的成像曲线作为对焦范围的上下限曲线，对应变倍镜位置x分别拟合对焦上限曲线g1（x）与下限曲线g2（x）;2）预判定搜索方向:上下限曲线的中间值g（x）=［g1（x）+g2（x）］/2，由几何概率论可知，最佳成像位置落在大范围的概率较大，因此，对焦镜头首先向g（x）方向搜索;3）一直搜索到上/下限曲线处，如果最佳成像位置是第一个点，那么可能落在另一边，再返回另一边搜索，否则，找到最佳成像位置即可完成对焦搜索。

图4 改进穷举搜索法Fig 4 Improved exhaustive search method

2．2 改进的爬山搜索法

爬山搜索法能够实现简单快速的对焦，但却容易陷入局部峰值。改进的爬山搜索，目标是不影响速度的前提下尽可能避免对焦搜索陷入局部峰值。

改进的爬山搜索法步骤如下:1）与改进的穷举搜索法类似，设定对焦范围上下限，并预判定搜索方向;2）判断到评价函数值下降两次才认为已经越过峰值，且上一次评价值小于下一次评价值乘以一个阈值才认为是下降，即F（n－1）＜T·F（n）且F（n）＜T·F（n+1）（F（n）为第n次的评价函数值，T为阈值，本文使用阈值为0．7）;3）先用大步搜索，再小步搜索。

改进的爬山搜索法，一定程度上可避免落入偶尔出现的局部峰值，显然，下降两次或更多次才返回更能克服陷入局部峰值，但会影响对焦实时性和使图像晃荡严重影响可观性。

2．3 增强抗干扰性能

一系列改进的搜索算法能够明显提高对焦速度与稳定性，但是仍存在更快的场景变换。对焦过程中场景内容发生变化产生干扰而导致对焦失败，其本质原因是:对焦搜索没完成前，场景变化导致评价函数值下降，搜索算法误认为已经找到评价曲线的下降点从而找到了评价曲线峰值，于是返回峰值位置。但实际上并没有找到真正的峰值，从而导致对焦失败。例如:当镜头对着人物进行对焦的过程还没完成，人物突然离开，镜头对着的是人物的背景，此时背景的评价值比人物的评价值要低，搜索算法会误认为已经过了峰值，显然，这是错误的。

本文采用2种措施提高抗干扰能力:

图5 抗干扰示意图Fig 5 Schematic diagram of interference

其二，当监控画面低于一定的光照度，一般对焦算法都无法准确对焦，继续搜索会导致乱对焦甚至卡镜头等情况。本文通过判定对焦区域的平均光强，当平均小于设定的阈值（亮度范围为0～255，本文设定为30）时，不进行对焦搜索。

2．4 调节变倍镜的快速对焦

具有光学变倍的镜头，如果已知多条成像曲线，准焦的情况下变倍镜变倍时，根据成像曲线可快速找到准焦的位置，节省了对焦搜索过程中判定方向和评价图像的运算时间。已知对焦范围内的多条成像曲线、变倍镜位置x与变焦镜位置y，可知变倍镜与变焦镜在某一条成像曲线y=f（x）上，一旦变倍镜变倍改变x，根据成像曲线y=f（x）相应移动变焦镜到准焦的位置，即可实现快速对焦。

3 综合的对焦搜索算法

考虑各种情况改进搜索算法，实际应用中是联合多种改进的对焦搜索算法，且使用先大步再小步的搜索策略。具体做法如下:1）图像非常暗或者场景无发生变化或者设置为手动对焦的时候，不启动对焦搜索;2）上次对完焦的评价函数值低于阈值时表示陷入局部峰值，启用改进的无穷搜索法;3）场景改变且基本处于静止状态，启用改进的爬山搜索法;4）对焦搜索后，判断图像是否误对焦，误对焦则返回继续搜索，否则，对焦结束。

4 实验与结果

使用HIS分析法与能量评价函数的对焦评价函数［4］，使用本文提出的综合搜索法进行对焦准确度、对焦速度与抗干扰性能力测试。

4．1 对焦准确度测试

采用室内与室外景物进行对焦测试，图6与7给出了对焦前后的对比图像，可见本系统都能够很好地完成自动对焦。

4．2 对焦速度测试

对焦速度决定着对焦系统的实时性。采用距离为1．5 m，照度分别为 57．5，28．5，0．9，0．47lx 下各进行 20 次对焦测试，如图8所示，可知其具有较快的对焦速度:只在极端低照度0．47lx时需要约3s完成对焦，一般情况下都可以在1 s左右完成对焦。因此，0．47lx是光照度的临界值，低于此临界值不启动对焦搜索，对焦镜保持原位不动。

4．3 抗干扰性能与稳健性测试

采用各种不同的极端条件测试系统的抗干扰能力:1）搜索过程中，用不同速度的物体改变对焦场景来达到干扰对焦过程;2）近距离挡住对焦镜头一定的时间，迅速放开让镜头对焦远处场景;3）室内与室外来回快速切换场景;4）在室内不断地开关日光灯和在低照度的环境下测试对焦。测试结果表明:研发出的综合对焦搜索算法基本上可以抵抗干扰，并且快速重新完成对新场景对焦。

5 结论

优秀的对焦搜索算法应该使自动对焦具备良好的准确性、实时性及抗干扰性等特点。本文引入对焦范围与成像曲线的概念，改进了传统的爬山搜索法与穷举搜索法，并使用先大步后小步地搜索，能够避免搜索过程陷入对焦曲线的局部峰值和提高对焦速度;利用成像曲线可使变倍镜移动时实现快速地对焦;针对各种误对焦的可能性，采用搜索结束再校验图像的方法和在低于一定光照度的情况下停止搜索，可以增强算法的抗干扰性能力;最后把几种搜索方法联合使用，即综合的对焦搜索算法，其理论依据充分。在实验中，针对室内外不同的景物进行对焦准确度、速度及抗干扰性测试，均得到较理想的效果。

图6 室内景物Fig 6 Indoor scene

图7 室外景物Fig 7 Outdoor scene

图8 对焦速度测试示意图Fig 8 Schematic diagram of the focusing speed test

［1］ 李 奇．数字自动对焦技术的理论及实现方法研究［D］．杭州:浙江大学，2004．

［2］ 蒋 婷．基于图像处理的自动对焦理论和技术研究［D］．武汉:武汉理工大学，2008．

［3］ 王立强，林 斌，徐向东，等．基于USB Video Camera的自动对焦系统［J］．光电工程，2001，28（5）:32 －34．

［4］ 王剑华，邓华秋，邓云龙，等．低信噪比环境下的实时聚焦方法研究［J］．光学技术，2010，36（6）:932 －935．