I am trying to implement section 3.4 of paper Predicting Important Objects for Egocentric Video Summarization where they have created a distance matrix of frame histograms.

In short, let say is mean of distances between all frames,DVis distance matrix.

I didn't understand what is meant by this:

We next perform complete-link agglomerative clustering with DV , grouping frames until the smallest maximum interframe distance is larger than two standard deviations beyond Ω

Can this be achieved by setting the cutoff value to 2Ω in Matlab's clusterdata function ?


1 Answer 1


Clearly, 2 standard deviations beyond Omega is not the same as twice the mean.

Apparently, their process is this:

  1. compute the distance matrix
  2. compute the mean
  3. compute the standard deviation
  4. compute hierarchical clustering with maximum linkage
  5. cut the tree at mu+2*sigma

Because complete linkage is in O(n^3), this approach will not scale to longer videos or higher frame rates.

  • $\begingroup$ What did you mean by saying "Because complete linkage is in O(n^3), this approach will not scale to longer videos or higher frame rates." Does that mean I should not use complete linkage in long videos just for "performance" issues ? $\endgroup$ Oct 22, 2015 at 20:31
  • 1
    $\begingroup$ Yes, this approach will not scale to large data because it has cubic complexity. $\endgroup$ Oct 22, 2015 at 21:00
  • $\begingroup$ If you look at their paper, they decreased the framerate, and used only 680 frames on average (assuming they only used the annotated frames for clustering). At 24 fps, this would be less than 30 seconds of video. O(n^3) means that 10x as many frames will take 1000x as long. $\endgroup$ Oct 22, 2015 at 21:30
  • $\begingroup$ I think they took every 15th frame.I also did same thing and took every 15th frame this decreased the run time of my code. $\endgroup$ Oct 22, 2015 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.