Computational running time

The object detection is done by a spatiotemporal separable convolution (section 2). Hence the cost is: $O(n_{fr} \cdot n_{pix})$, where $n_{fr}$, $n_{pix}$ are the number of frames in the video, the number of pixels in an image frame. The complexity of the K-means algorithm is $O(n_{fr} \cdot K \cdot m^2)$, where $K$, $m$, $i_{k}$ are respectively the number of prototype vectors, the size of the histograms ($m \times m$) and the number of iterations. Building the co-occurrance and the similarity matrix has a cost of $O(n_{fr} + d \cdot K^2)$. Finally finding the second eigenvector of a symmetrical sparse $n \times n$ matrix takes $O(n^{\frac{3}{2}} )$ time, where $n = N+K$. For example, the running times for the 20 hours road video are: 8 hours 40 minutes (object detection), 1 hours 36 minutes (K-means) and 3 seconds (eigensolver) on a Pentium IV 2.4GHz.