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 ?


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.

| improve this answer | |
  • $\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$ – Muhammet Ali Asan Oct 22 '15 at 20:31
  • 1
    $\begingroup$ Yes, this approach will not scale to large data because it has cubic complexity. $\endgroup$ – Has QUIT--Anony-Mousse Oct 22 '15 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$ – Has QUIT--Anony-Mousse Oct 22 '15 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$ – Muhammet Ali Asan Oct 22 '15 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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