數(shù)字自動對焦中的搜索算法研究

王劍華，鄧華秋，陳參寧

（華南理工大學(xué) 物理系，廣東廣州 510640）

0 引言

伴隨IT技術(shù)的高速發(fā)展，微電子技術(shù)、數(shù)字圖像處理及網(wǎng)絡(luò)傳輸技術(shù)的發(fā)展，各行業(yè)對數(shù)字視頻監(jiān)控技術(shù)的智能需求也不斷發(fā)展。自動對焦作為視頻監(jiān)控的關(guān)鍵技術(shù)之一，已經(jīng)廣泛地應(yīng)用于一體化視頻監(jiān)控、數(shù)碼相機、測距等領(lǐng)域中。與測距法和聚焦檢測法的傳統(tǒng)自動對焦方法相比，基于數(shù)字圖像處理的自動對焦方法更加靈活方便，有利于設(shè)備的集成化、微型化及降低設(shè)備的成本。

數(shù)字自動對焦中，作為自動控制關(guān)鍵技術(shù)的搜索算法，其最終目標(biāo)是找到對焦評價曲線峰值。對焦搜索過程就是通過比較一系列離散的對焦評價函數(shù)值，然后根據(jù)分析結(jié)果反饋控制對焦鏡移動，實質(zhì)上也是一維極值的最優(yōu)化問題［1］。

本文通過對典型對焦搜索算法進行研究，改進傳統(tǒng)搜索算法，力求設(shè)計出優(yōu)秀的綜合對焦搜索算法，目的是為了避免搜索落入對焦曲線局部峰值、提高對焦速度及增強對焦抗干擾性能力。

1 典型的對焦搜索算法

典型的對焦搜索算法有窮舉搜索法、爬山搜索法、Fibonacci搜索法和函數(shù)逼近法等［2］。

1．1 窮舉搜索法

窮舉搜索法是最簡單與直接的對焦搜索法，示意圖如圖1所示，搜索區(qū)間［a，b］分成若干等間隔的子區(qū)間，利用對焦評價函數(shù)評價所有區(qū)間端點的圖像，從得到的所有評價值集合中求出最大值，即是準(zhǔn)焦的位置。

窮舉搜索法具備的優(yōu)點是相對簡單;步長固定不變，便于計算機自動控制;無窮搜索特點也不受局部峰值的影響。存在的缺點是計算量大，不適用于實時的對焦搜索。

1．2 爬山搜索法

圖1 窮舉搜索法示意圖Fig 1 Schematic diagram of an exhaustive search method

爬山搜索法的前提是對焦評價函數(shù)具有單峰性、單調(diào)性。作為應(yīng)用最廣泛的一種搜索法，典型示意圖如圖2所示。首先，對焦鏡頭向兩邊方向搜索，評價值增大的方向即為正確的方向，找到鏡頭搜索方向;其次，對焦鏡頭越過評價曲線鋒值，縮小步進距離，往回搜索并再次越過峰值;最后，縮小步進距離，反復(fù)搜索，一直到滿足精度要求的峰值即為成像準(zhǔn)焦的位置。

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

爬山搜索法的優(yōu)點是簡單易實現(xiàn)，計算量也易于控制，適合于實時的快速對焦。存在著的缺點是容易陷入到由于噪聲等干擾引起的局部峰值附近，導(dǎo)致對焦失敗。

Fibonacci搜索法具有存儲量少、容易預(yù)測不確定區(qū)間等優(yōu)點，但卻容易陷入局部峰值，也由于非整步長和對電機的分辨力要求太高而難以實現(xiàn)，只能作為設(shè)計搜索算法的參考依據(jù)。函數(shù)逼近法的最佳用法，是利用峰值左右的幾個值，擬合曲線求極值，得到最佳成像位置［3］。

2 基于傳統(tǒng)對焦搜索算法的改進

本文是對具有光學(xué)變倍的鏡頭進行自動對焦研究，鏡頭結(jié)構(gòu)示意圖如圖3所示。對焦景物從前固定組進入鏡頭，經(jīng)變倍鏡、光圈、對焦鏡及后固定組成像在圖像探測器上，變倍鏡可以調(diào)節(jié)所成像的大小，對焦鏡能夠調(diào)節(jié)使圖像探測器上所成像達到準(zhǔn)焦。由鏡頭設(shè)計廠商或者手動測量獲得不同物距的成像曲線，即一定物距的景物，對應(yīng)不同的變倍鏡位置都有一個最佳的變焦鏡位置使所成像準(zhǔn)焦。

窮舉搜索法不易受干擾，但卻不利于實時性;爬山搜索利于實時要求較高的對焦，但卻容易受干擾而陷入局部峰值。對傳統(tǒng)搜索法的改進，目的是為了提高對焦收斂速度與增強抗干擾能力。

2．1 改進的窮舉搜索法

圖3 鏡頭結(jié)構(gòu)示意圖Fig 3 Schematic diagram of the lens’structure

本文把對焦鏡可移動范圍稱為對焦范圍。對焦范圍過寬會導(dǎo)致:1）對焦收斂速度過慢，例如窮舉搜索法;2）對焦鏡遠(yuǎn)離光學(xué)對焦范圍會使對焦曲線較平坦甚至出現(xiàn)多處局部峰值，搜索算法極有可能會陷入局部峰值誤對焦甚至再也無法正常對焦。對焦鏡遠(yuǎn)離光學(xué)對焦范圍情況下，用爬山搜索等方法無法正常搜索，本文采用改進的窮舉搜索法，主要是在對焦范圍內(nèi)設(shè)定上下限，并預(yù)判定搜索方向，可以避免對焦鏡遠(yuǎn)離光學(xué)范圍與提高收斂速度。

改進的窮舉搜索法如圖4所示:1）獲取最近（例如:1 m）與最遠(yuǎn)處的成像曲線作為對焦范圍的上下限曲線，對應(yīng)變倍鏡位置x分別擬合對焦上限曲線g1（x）與下限曲線g2（x）;2）預(yù)判定搜索方向:上下限曲線的中間值g（x）=［g1（x）+g2（x）］/2，由幾何概率論可知，最佳成像位置落在大范圍的概率較大，因此，對焦鏡頭首先向g（x）方向搜索;3）一直搜索到上/下限曲線處，如果最佳成像位置是第一個點，那么可能落在另一邊，再返回另一邊搜索，否則，找到最佳成像位置即可完成對焦搜索。

圖4 改進窮舉搜索法Fig 4 Improved exhaustive search method

2．2 改進的爬山搜索法

爬山搜索法能夠?qū)崿F(xiàn)簡單快速的對焦，但卻容易陷入局部峰值。改進的爬山搜索，目標(biāo)是不影響速度的前提下盡可能避免對焦搜索陷入局部峰值。

改進的爬山搜索法步驟如下:1）與改進的窮舉搜索法類似，設(shè)定對焦范圍上下限，并預(yù)判定搜索方向;2）判斷到評價函數(shù)值下降兩次才認(rèn)為已經(jīng)越過峰值，且上一次評價值小于下一次評價值乘以一個閾值才認(rèn)為是下降，即F（n－1）＜T·F（n）且F（n）＜T·F（n+1）（F（n）為第n次的評價函數(shù)值，T為閾值，本文使用閾值為0．7）;3）先用大步搜索，再小步搜索。

改進的爬山搜索法，一定程度上可避免落入偶爾出現(xiàn)的局部峰值，顯然，下降兩次或更多次才返回更能克服陷入局部峰值，但會影響對焦實時性和使圖像晃蕩嚴(yán)重影響可觀性。

2．3 增強抗干擾性能

一系列改進的搜索算法能夠明顯提高對焦速度與穩(wěn)定性，但是仍存在更快的場景變換。對焦過程中場景內(nèi)容發(fā)生變化產(chǎn)生干擾而導(dǎo)致對焦失敗，其本質(zhì)原因是:對焦搜索沒完成前，場景變化導(dǎo)致評價函數(shù)值下降，搜索算法誤認(rèn)為已經(jīng)找到評價曲線的下降點從而找到了評價曲線峰值，于是返回峰值位置。但實際上并沒有找到真正的峰值，從而導(dǎo)致對焦失敗。例如:當(dāng)鏡頭對著人物進行對焦的過程還沒完成，人物突然離開，鏡頭對著的是人物的背景，此時背景的評價值比人物的評價值要低，搜索算法會誤認(rèn)為已經(jīng)過了峰值，顯然，這是錯誤的。

本文采用2種措施提高抗干擾能力:

圖5 抗干擾示意圖Fig 5 Schematic diagram of interference

其二，當(dāng)監(jiān)控畫面低于一定的光照度，一般對焦算法都無法準(zhǔn)確對焦，繼續(xù)搜索會導(dǎo)致亂對焦甚至卡鏡頭等情況。本文通過判定對焦區(qū)域的平均光強，當(dāng)平均小于設(shè)定的閾值（亮度范圍為0～255，本文設(shè)定為30）時，不進行對焦搜索。

2．4 調(diào)節(jié)變倍鏡的快速對焦

具有光學(xué)變倍的鏡頭，如果已知多條成像曲線，準(zhǔn)焦的情況下變倍鏡變倍時，根據(jù)成像曲線可快速找到準(zhǔn)焦的位置，節(jié)省了對焦搜索過程中判定方向和評價圖像的運算時間。已知對焦范圍內(nèi)的多條成像曲線、變倍鏡位置x與變焦鏡位置y，可知變倍鏡與變焦鏡在某一條成像曲線y=f（x）上，一旦變倍鏡變倍改變x，根據(jù)成像曲線y=f（x）相應(yīng)移動變焦鏡到準(zhǔn)焦的位置，即可實現(xiàn)快速對焦。

3 綜合的對焦搜索算法

考慮各種情況改進搜索算法，實際應(yīng)用中是聯(lián)合多種改進的對焦搜索算法，且使用先大步再小步的搜索策略。具體做法如下:1）圖像非常暗或者場景無發(fā)生變化或者設(shè)置為手動對焦的時候，不啟動對焦搜索;2）上次對完焦的評價函數(shù)值低于閾值時表示陷入局部峰值，啟用改進的無窮搜索法;3）場景改變且基本處于靜止?fàn)顟B(tài)，啟用改進的爬山搜索法;4）對焦搜索后，判斷圖像是否誤對焦，誤對焦則返回繼續(xù)搜索，否則，對焦結(jié)束。

4 實驗與結(jié)果

使用HIS分析法與能量評價函數(shù)的對焦評價函數(shù)［4］，使用本文提出的綜合搜索法進行對焦準(zhǔn)確度、對焦速度與抗干擾性能力測試。

4．1 對焦準(zhǔn)確度測試

采用室內(nèi)與室外景物進行對焦測試，圖6與7給出了對焦前后的對比圖像，可見本系統(tǒng)都能夠很好地完成自動對焦。

4．2 對焦速度測試

對焦速度決定著對焦系統(tǒng)的實時性。采用距離為1．5 m，照度分別為 57．5，28．5，0．9，0．47lx 下各進行 20 次對焦測試，如圖8所示，可知其具有較快的對焦速度:只在極端低照度0．47lx時需要約3s完成對焦，一般情況下都可以在1 s左右完成對焦。因此，0．47lx是光照度的臨界值，低于此臨界值不啟動對焦搜索，對焦鏡保持原位不動。

4．3 抗干擾性能與穩(wěn)健性測試

采用各種不同的極端條件測試系統(tǒng)的抗干擾能力:1）搜索過程中，用不同速度的物體改變對焦場景來達到干擾對焦過程;2）近距離擋住對焦鏡頭一定的時間，迅速放開讓鏡頭對焦遠(yuǎn)處場景;3）室內(nèi)與室外來回快速切換場景;4）在室內(nèi)不斷地開關(guān)日光燈和在低照度的環(huán)境下測試對焦。測試結(jié)果表明:研發(fā)出的綜合對焦搜索算法基本上可以抵抗干擾，并且快速重新完成對新場景對焦。

5 結(jié)論

優(yōu)秀的對焦搜索算法應(yīng)該使自動對焦具備良好的準(zhǔn)確性、實時性及抗干擾性等特點。本文引入對焦范圍與成像曲線的概念，改進了傳統(tǒng)的爬山搜索法與窮舉搜索法，并使用先大步后小步地搜索，能夠避免搜索過程陷入對焦曲線的局部峰值和提高對焦速度;利用成像曲線可使變倍鏡移動時實現(xiàn)快速地對焦;針對各種誤對焦的可能性，采用搜索結(jié)束再校驗圖像的方法和在低于一定光照度的情況下停止搜索，可以增強算法的抗干擾性能力;最后把幾種搜索方法聯(lián)合使用，即綜合的對焦搜索算法，其理論依據(jù)充分。在實驗中，針對室內(nèi)外不同的景物進行對焦準(zhǔn)確度、速度及抗干擾性測試，均得到較理想的效果。

圖6 室內(nèi)景物Fig 6 Indoor scene

圖7 室外景物Fig 7 Outdoor scene

圖8 對焦速度測試示意圖Fig 8 Schematic diagram of the focusing speed test

［1］ 李 奇．?dāng)?shù)字自動對焦技術(shù)的理論及實現(xiàn)方法研究［D］．杭州:浙江大學(xué)，2004．

［2］ 蔣 婷．基于圖像處理的自動對焦理論和技術(shù)研究［D］．武漢:武漢理工大學(xué)，2008．

［3］ 王立強，林 斌，徐向東，等．基于USB Video Camera的自動對焦系統(tǒng)［J］．光電工程，2001，28（5）:32 －34．

［4］ 王劍華，鄧華秋，鄧云龍，等．低信噪比環(huán)境下的實時聚焦方法研究［J］．光學(xué)技術(shù)，2010，36（6）:932 －935．