Viola-Jones算法复杂度

Question

以O(log(N))形式表示的Viola-Jones算法复杂度是多少？尽管这是一个非常简单的算法，但没有关于它的具体信息。

Answer 1

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

Answer 2

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

1. Haar Feature Selection
2. Creating an Integral Image
3. Adaboost

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

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

第三步的复杂度是O(N D^2)，其中D是look here为什么的特征数量。

第四步的复杂度低于O(N) here为什么。

总而言之，我们可以从每个阶段计算出维奥拉-琼斯算法的复杂度是O(n)