📚 课程目录第4章斐波那契搜索

4、斐波那契搜索：黄金分割法（Fibonacci Search）原理、在AF中的应用、收敛性分析

说到自动对焦的搜索策略，很多人第一反应就是爬山法。但爬山法有个硬伤——它容易卡在局部极值。尤其是当你面对的是那种多峰的对比度曲线，比如镜头在微距和无穷远之间来回震荡时，爬山法基本就废了。

那怎么办？我个人的习惯是，遇到这种“单峰但不确定范围”的问题，优先考虑斐波那契搜索。说白了，它就是一种在已知区间内寻找单峰函数极值的高效方法。你想想看，镜头从近端到远端，对比度曲线通常就是单峰的——至少理想情况下是。那斐波那契搜索就是为这种场景量身定做的。

4.1 斐波那契搜索的核心原理

斐波那契搜索，也叫黄金分割法。它利用斐波那契数列来逐步缩小区间。每次迭代，它会在当前区间内取两个点，比较它们的函数值，然后丢掉“不可能是极值”的那一段。

为什么用斐波那契数列？因为它的比值会收敛到黄金分割比 0.618。这个比例有个特性：每次缩小区间后，保留下来的那部分长度与总长度的比值是固定的。这样就能保证搜索效率最大化。

我画了一张图，帮你理解这个过程：

你看，每次迭代后，区间长度都会按斐波那契数列的比值缩小。经过 n 次迭代，区间长度会缩小到原来的 1/F(n+1)。这意味着什么？如果你想要 1 微米的精度，只需要算一下需要多少次迭代就行。

4.2 在自动对焦中的具体应用

在 AF 系统里，我们通常把镜头行程映射到 [0, 1] 区间。然后在这个区间内搜索对比度最高的位置。

具体步骤是这样的：

确定搜索范围：比如镜头从近端到远端，对应步数 0 到 1000。
计算斐波那契数列：根据需要的精度，确定迭代次数 n。
取两个测试点：按照斐波那契比值，在区间内取 x1 和 x2。
计算对比度：在 x1 和 x2 位置分别采集图像，计算对比度值。
比较并缩小区间：如果 f(x1) > f(x2)，则丢掉 [x2, b]；否则丢掉 [a, x1]。
重复：直到区间长度小于预设阈值。

我贴一段伪代码，方便你理解：

function fibonacciSearch(a, b, n):
    // 生成斐波那契数列
    fib = [0, 1]
    for i = 2 to n+1:
        fib.append(fib[i-1] + fib[i-2])
    
    // 初始化两个测试点
    x1 = a + (fib[n-2] / fib[n]) * (b - a)
    x2 = a + (fib[n-1] / fib[n]) * (b - a)
    
    // 计算对比度
    f1 = computeContrast(x1)
    f2 = computeContrast(x2)
    
    for k = n-1 down to 2:
        if f1 > f2:
            // 极值在 [a, x2] 之间
            b = x2
            x2 = x1
            f2 = f1
            x1 = a + (fib[k-2] / fib[k]) * (b - a)
            f1 = computeContrast(x1)
        else:
            // 极值在 [x1, b] 之间
            a = x1
            x1 = x2
            f1 = f2
            x2 = a + (fib[k-1] / fib[k]) * (b - a)
            f2 = computeContrast(x2)
    
    // 返回最终位置
    return (a + b) / 2

我的经验：实际项目中，我一般把 n 设为 10 到 15。对于大多数手机镜头模组，10 次迭代就能把精度控制在 10 微米以内。再多迭代，收益就很小了，反而浪费时间。

4.3 收敛性分析

斐波那契搜索的收敛速度是线性的，但它的线性系数非常接近 0.618。这意味着每次迭代，区间长度大约缩小到原来的 61.8%。

我整理了一个对比表，让你直观感受一下：

迭代次数	区间剩余比例	精度（初始范围 1000 步）
5	12.5%	125 步
10	1.5%	15 步
15	0.18%	1.8 步
20	0.02%	0.2 步

看到没？15 次迭代后，精度已经到 1.8 步了。对于大多数 AF 系统来说，这已经足够了。

为什么收敛这么快？因为斐波那契搜索每次迭代只需要计算两个点的函数值，而且这两个点中有一个可以复用上一次的结果。你想想看，每次迭代只需要一次新的对比度计算，效率非常高。

关键结论：斐波那契搜索的收敛速度是 O(log n)，但它的常数因子比二分法小得多。对于单峰函数，它是最优的搜索策略——没有之一。

4.4 实际应用中的注意事项

嗯，这里要注意。斐波那契搜索虽然好，但它有个前提：对比度曲线必须是单峰的。如果遇到多峰的情况，比如镜头有灰尘或者光线不均匀，那它就会失效。

我曾经在一个项目中遇到过这个问题。当时是户外强光环境，对比度曲线出现了两个峰值。斐波那契搜索直接收敛到了错误的峰值上，导致画面模糊。后来我加了一个预处理步骤：先做一次粗扫描，确定主峰的大致位置，然后再用斐波那契搜索精确定位。

避坑指南：斐波那契搜索对噪声敏感。如果对比度计算有较大波动，建议先做平滑处理。我一般用 3 帧平均，效果不错。

另外，斐波那契搜索需要预先知道迭代次数 n。这个 n 怎么选？我个人的习惯是：

对于手机摄像头：n = 10 ~ 12
对于监控摄像头：n = 12 ~ 15
对于工业相机：n = 15 ~ 20

当然，你也可以动态调整。比如先设 n = 10，如果收敛后精度不够，再继续迭代。不过这样做会破坏斐波那契数列的连续性，效率会打折扣。

最后说一句，斐波那契搜索和黄金分割法本质上是同一回事。区别只在于：斐波那契搜索用离散的斐波那契数列，黄金分割法用连续的黄金分割比。在实际的嵌入式系统中，斐波那契搜索更容易实现，因为它只需要整数运算。