1. A system to perform hierarchical video segmentation, comprising: a processor coupled to a camera; wherein the processor executes: 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 probabilistic histograms combinable in a graph-based framework; and applying a max-margin cue combination that learns a supervised distance metric for region dissimilarity that combines color, flow and trajectory features; generating a max-margin distance metric for video segmentation that combines a plurality of feature channels; determining feature representation φ(S) for a segment S as a stacked up histograms from all the individual cues; learning feature weighting as a linear combination w T |φ(S i )−φ(S j ), where an optimal weight w* is determined by solving an optimization problem of the form: ⁢ min w , ξ ij 1 2 ⁢ w T ⁢ w + λ N + ⁢ ∑ i , j ⁢ ⁢ ξ ij + + λ N - ⁢ ∑ i , j ⁢ ⁢ ξ ij - s. t. y ij ⁢ w T ⁢  ϕ ⁡ ( s i ) - ϕ ⁡ ( s j )  ≤ 2 ⁢ ⁢ y ij - 1 + ξ ij , ∀ i , j w ± 0 , ξ ij ≥ 0 , ⁢ where ξ ij denote slack variables and λ is a soft margin trade-off parameter, N + and N − are the number of pairs of segments that have the same or different ground truth label and ξ ij + , ξ ij − are slack variables with respective membership in those positive or negative sets.