Viola-Jones algorithm complexity

Question

What is Viola-Jones algorithm complexity in form like O(log(N))? Even though it's a preety simple algorithm there is no concrete info about it.

Answer 1

It's linear (O(N)) in the number (N) of pixels of the input image. All Haar image features are computed in constant time upon the integral image, and computing the latter requires one pass over the input image.

Answer 2

When we toking about Viola-Jones algorithm complexity we need to remember the steps of this algorithm. According to the original article of Paul Viola and Michael Jones, the algorithm contains 4 main steps:

1. Haar Feature Selection
2. Creating an Integral Image
3. Adaboost Training
4. Cascading Classifiers

The complexity of the first step is O(1) because the decision of which Haar Feature to choose is not related to the input.

The complexity of the second step is O(N) because in this step we go over the image matrix. As you know, an Integral Image helps us to perform computations on all the pixels inside that particular feature in O(1) complexity. However, the creation of Integral Image cost O(N) because we go over each pixel in the original matrix and write in the new matrix new value. The value of each point in the new matrix is the sum of all pixels above and to the left, including the target pixel in the old matrix

The complexity of the third step is O(N D^2), where D is the number of features look here why.

The complexity of the fourth step is less than O(N) look here why.

To sum up, as we can calculate from each stage the complexity of the Viola-Jones algorithm is O(n)