數字自動對焦中的搜索算法研究

王劍華，鄧華秋，陳參寧

（華南理工大學 物理系，廣東廣州 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．