computer-vision - Viola-Jones 算法复杂度

Question

像 O(log(N)) 这样的形式的 Viola-Jones 算法复杂度是多少？即使它是一个非常简单的算法，也没有关于它的具体信息。

Answer 1

它在输入图像的像素数 (N) 中是线性的 (O(N))。所有 Haar 图像特征都是在积分图像上以恒定时间计算的，计算后者需要对输入图像进行一次遍历。

Answer 2

当我们谈论 Viola-Jones 算法的复杂性时，我们需要记住该算法的步骤。根据 Paul Viola 和 Michael Jones 的原始文章，该算法包含 4 个主要步骤：

1. 哈尔特征选择
2. 创建一个完整的图像
3. Adaboost 训练
4. 级联分类器

第一步的复杂度是 O(1)，因为选择哪个 Haar 特征的决定与输入无关。

第二步的复杂度是 O(N)，因为在这一步中我们遍历图像矩阵。如您所知，积分图像可帮助我们以 O(1) 复杂度对特定特征内的所有像素执行计算。然而，积分图像的创建成本 O(N)，因为我们遍历原始矩阵中的每个像素并在新矩阵中写入新值。新矩阵中每个点的值是左上角所有像素的总和，包括旧矩阵中的目标像素

第三步的复杂度是O(ND^2)，其中D是特征的数量看这里为什么。

第四步的复杂度小于 O(N) 看这里为什么。

综上所述，我们可以从每个阶段计算 Viola-Jones 算法的复杂度为O(n)