A method to perform hiearchical video segmentation includes: defining voxels over a spatio-temporal video; grouping into segments contiguous voxels that display similar characteristics including similar appearance or motion; determining a trajectory-based feature that complements color and optical flow cues, wherein trajectory cues are probabilistically meaningful histograms combinable for use in a graph-based framework; and applying a max-margin module for cue combination that learns a supervised distance metric for region dissimilarity that combines color, flow and trajectory features.